package graph;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * O(v*e^2) Based on EdmondsKarp solution
 * 
 * Calculate MinCost is just like finding the shortest path in the remaining
 * graph (bellman-ford solution here)
 * 
 * @author yinzichen
 * 
 */
public class MinCostMaxFlow {

	/**
	 * 
	 * @param capacity
	 *            network flow capacity
	 * @param cost
	 *            1 unit flow's cost, cost[i][j] = -cost[j][i]
	 * @param vertexNum
	 * @param src
	 * @param dest
	 * @return
	 */

	public static int[] minCostMaxFlow(int[][] capacity, int[][] cost,
			int vertexNum, int src, int dest) {
		int[][] remain = new int[vertexNum][vertexNum];
		for (int i = 0; i < vertexNum; i++) {
			for (int j = 0; j < vertexNum; j++) {
				remain[i][j] = capacity[i][j];
			}
		}
		int totFlow = 0, totCost = 0;
		Queue<Integer> q = new LinkedList<Integer>();
		int[] prev = new int[vertexNum];
		int[] flow = new int[vertexNum];
		int[] minCost = new int[vertexNum];
		boolean[] used = new boolean[vertexNum];
		while (true) {
			Arrays.fill(used, false);
			Arrays.fill(minCost, Integer.MAX_VALUE);
			used[src] = true;
			minCost[src] = 0;
			flow[src] = Integer.MAX_VALUE;
			q.clear();
			q.add(src);
			while (!q.isEmpty()) {
				int u = q.poll();
				used[u] = false;
				for (int v = 0; v < vertexNum; v++) {
					if (remain[u][v] > 0
							&& minCost[v] > minCost[u] + cost[u][v]) {
						flow[v] = Math.min(flow[u], remain[u][v]);
						minCost[v] = minCost[u] + cost[u][v];
						prev[v] = u;
						if (!used[v]) {
							used[v] = true;
							q.add(v);
						}
					}
				}
			}
			if (flow[dest] == 0)
				break;
			for (int i = dest; i != src; i = prev[i]) {
				remain[prev[i]][i] -= flow[dest];
				remain[i][prev[i]] += flow[dest];
			}
			totFlow += flow[dest];
			totCost += minCost[dest] * flow[dest];
		}
		return new int[] { totFlow, totCost };
	}
}
